#include "stdafx.h"

#include "Utils.h"

int men[N][N] = { 0 };

int minDstDP2(int i, int j, int w[N][N]) { //call (n-1, n-1)
	
	if (i == 0 && j == 0)
		return w[0][0];

	if (men[i][j] > 0) //eliminate duplicate calculation
		return men[i][j];

	int minLeft = INT32_MAX;
	if (j - 1 >= 0)
		minLeft = minDstDP2(i, j - 1, w);

	int minUp = INT32_MAX;
	if (i - 1 >= 0)
		minUp = minDstDP2(i - 1, j, w);

	int currentDst = w[i][j] + MIN(minLeft, minUp);
	men[i][j] = currentDst;

	return currentDst;
}